package com.Sun.Model;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;


import com.Sun.Helper.searchHelper;
public class indexTree implements Serializable {
	private static final long serialVersionUID = 3L;
	private indexTreeNode root;
	public indexTree(){}
	public indexTree(indexTreeNode root)
	{
		this.root=root;
	} 
	public indexTreeNode getRoot()
	{
		return root;
	}
	public void setIndexNode(indexTreeNode root)
	{
		this.root=root;
	}
	/**
	 * 得到以node为根节点的树的深度
	 * @param node
	 * @return
	 */
	public int getTreeDepth(indexTreeNode node)
	{
		int leftDepth=0;
		int rightDepth=0;
		if(node==null)
		{
			return 0;
		}
		else {
			leftDepth=getTreeDepth(node.getLeft())+1;
			rightDepth=getTreeDepth(node.getRight())+1;
			return leftDepth>rightDepth?leftDepth:rightDepth;
		}
	}
	/**
	 * 根据所有的叶子节点建立索引树
	 * @param queue
	 */
	public void buildBalanceBinTree(Queue<indexTreeNode> queue)
	{
		Queue<indexTreeNode> currNodeSet=queue;
		Queue<indexTreeNode> tempNodeSet=new LinkedBlockingQueue<indexTreeNode>();
		indexTreeNode tempNode1=new indexTreeNode();
		indexTreeNode tempNode2=new indexTreeNode();
		indexTreeNode newNode=new indexTreeNode();
		while(currNodeSet.size()>1)
		{
			if(currNodeSet.size()%2==0)
			{
				while(!currNodeSet.isEmpty())
				{
					tempNode1=currNodeSet.poll();
					tempNode2=currNodeSet.poll();
					newNode=getNewNode(tempNode1, tempNode2);
					tempNode1.setParent(newNode);
					tempNode2.setParent(newNode);
					tempNodeSet.add(newNode);
				}
			}
			else {
				while(currNodeSet.size()>3)
				{
					tempNode1=currNodeSet.poll();
					tempNode2=currNodeSet.poll();
				    newNode=getNewNode(tempNode1, tempNode2);
					tempNode1.setParent(newNode);
					tempNode2.setParent(newNode);
					tempNodeSet.add(newNode);
				}
				tempNode1=currNodeSet.poll();
				tempNode2=currNodeSet.poll();
				newNode=getNewNode(tempNode1, tempNode2);
				tempNode1.setParent(newNode);
				tempNode2.setParent(newNode);
				tempNode1=newNode;
				tempNode2=currNodeSet.poll();
				newNode=getNewNode(tempNode1, tempNode2);
				tempNode1.setParent(newNode);
				tempNode2.setParent(newNode);
				tempNodeSet.add(newNode);
			}
			int count=tempNodeSet.size();
			for(int i=0;i<count;i++)
			{
				currNodeSet.add(tempNodeSet.poll());
			}
			tempNodeSet.clear();
		}
		root=currNodeSet.poll();
	}
	/**
	 * 由节点node1和节点node2得到一个中间节点
	 * @param node1
	 * @param node2
	 * @return
	 */
	public  indexTreeNode getNewNode(indexTreeNode node1,indexTreeNode node2)
	{
	   int n=node1.getSearchIndex().length;
		indexTreeNode newNode=new indexTreeNode(n);
		double []searchIndex=new double[n];
		for(int i=0;i<n;i++)
		{
			//取相对较大的值
			if(node1.getSearchIndex()[i]>node2.getSearchIndex()[i])
			{
				searchIndex[i]=node1.getSearchIndex()[i];
			}
			else
			{
				searchIndex[i]=node2.getSearchIndex()[i];
			}
		}
		newNode.setSearchIndex(searchIndex);
		newNode.setLeft(node1);
		newNode.setRight(node2);
		return newNode;
	}
	/**
	 * 广度优先遍历索引树
	 * @param node
	 */
	public void levelOrder(indexTreeNode node)
	{
		Queue<indexTreeNode> queue=new LinkedBlockingQueue<indexTreeNode>();
		indexTreeNode currNode=node;
		if(currNode!=null)
		{
			queue.add(currNode);
		}
		while(!queue.isEmpty())
		{
			currNode=queue.poll();
			visit(currNode);
			if(currNode.getLeft()!=null)
			{
				queue.add(currNode.getLeft());
			}
			if(currNode.getRight()!=null)
			{
				queue.add(currNode.getRight());
			}
		}
		
	}
	/**
	 * 后序遍历索引树
	 * @param node
	 */
	public void postOrderNoTraverse(indexTreeNode node)
	{
		Stack< indexTreeNode>stack=new Stack<indexTreeNode>();
		indexTreeNode currNode=node;
		indexTreeNode preNode=null;
		while(!stack.isEmpty()||currNode!=null)
		{
			while(currNode!=null)
			{
				stack.push(currNode);
				currNode=currNode.getLeft();
			}
			currNode=stack.peek();//得到栈顶的元素
			//如果当前节点没有右孩子或者右孩子已经被访问过，那么访问当前节点
			if(currNode.getRight()==null||currNode.getRight()==preNode)
			{
				//currNode=stack.pop();
				visit(currNode);
				preNode=currNode;
				stack.pop();
				currNode=null;
			}
			else {
				currNode=currNode.getRight();
			}
			
		}
	}
	public void visit(indexTreeNode node)
	{
		if(node.getFID()!=null)
		{
			System.out.println(node.getFID());
		}
		else {
			System.out.println("内部节点");
		}
	}
	/**
	 * 得到树的所有的节点数
	 * @return
	 */
	public int getNodeCount()
	{
		int count=0;
		indexTreeNode currNode=root;
		Queue<indexTreeNode>queue=new LinkedBlockingQueue<indexTreeNode>();
		if(currNode!=null)
		{
			queue.add(currNode);
		}
		while(!queue.isEmpty())
		{
			currNode=queue.poll();
			count++;
			if(currNode.getLeft()!=null)
			{
				queue.add(currNode.getLeft());
			}
			if(currNode.getRight()!=null)
			{
				queue.add(currNode.getRight());
			}
		}
		return count;
	}
	/**
	 * 判断节点是否为叶子节点
	 * @param node
	 * @return
	 */
	public boolean isLeaf(indexTreeNode node)
	{
		if(node.getLeft()==null&&node.getRight()==null)
		{
			return true;
		}
		else {
			return false;
		}
	}
	/**
	 * 返回一个以node为根节点的子树的叶子节点
	 * @param node
	 * @return
	 */
	public indexTreeNode getALeafNode(indexTreeNode node)
	{
		indexTreeNode resultNode=new indexTreeNode();
		indexTreeNode currNode=node;
		while(currNode!=null)
		{
			if(currNode.getRight()== null&&currNode.getRight()==null)
			{
				resultNode=currNode;
			}
			currNode=currNode.getLeft();
		}
		return resultNode;
		
	}
	/**
	 * 通过后序遍历的方式找到fid=fileName的叶子节点
	 * @param root
	 * @param fileName
	 * @return
	 */
	public indexTreeNode getLeafNodeByFileName(indexTreeNode root,String fileName)
	{
		indexTreeNode leafNode=new indexTreeNode();
		indexTreeNode currNode=root;
		Queue<indexTreeNode>queue=new LinkedBlockingQueue<indexTreeNode>();
		if(currNode!=null)
		{
			queue.add(currNode);
		}
		while(!queue.isEmpty())
		{
			currNode=queue.poll();
			if(currNode.getLeft()==null&&currNode.getRight()==null)
			{
				if(currNode.getFID().equals(fileName))
				{
					leafNode=currNode;
					return leafNode;
				}
			}
			if(currNode.getLeft()!=null)
			{
				queue.add(currNode.getLeft());
			}
			if(currNode.getRight()!=null)
			{
				queue.add(currNode.getRight());
			}
		}
		return leafNode;
	}
	public void preTravel(indexTreeNode node)
	{
		indexTreeNode currNode=node;
		Stack<indexTreeNode>stack=new Stack<indexTreeNode>();
		while(!stack.isEmpty()||currNode!=null)
		{
			if(currNode!=null)
			{
				if(currNode.getLeft()==null&&currNode.getRight()==null)
				{
					System.out.println(currNode.getFID());
				}
				else{
					System.out.println("内部节点");
				}
				if(currNode.getRight()!=null)
				{
					stack.push(currNode.getRight());
				}
				currNode=currNode.getLeft();
			}
			else{
				currNode=stack.pop();
			}
		}
	}
	public List<fileScorePair>searchOverTree(indexTreeNode node,encryptedIndex trapdoor,int mostK)
	{
		int count=0;
		List<fileScorePair>relFileList=new ArrayList<fileScorePair>();
		double kth_score=0;
		indexTreeNode currNode=node;
		Stack<indexTreeNode>stack=new Stack<indexTreeNode>();
		while(!stack.isEmpty()||currNode!=null)
		{
			if(currNode!=null)
			{
				//如果是叶子节点
				if(currNode.getRight()==null&&currNode.getLeft()==null)
				{
					fileScorePair tempfileScore=new fileScorePair();
					double score=searchHelper.getScore(currNode.getEnIndex(), trapdoor);
					count++;
					tempfileScore.setFileName(currNode.getFID());
					tempfileScore.setScore(score);
				   searchHelper.update(relFileList, tempfileScore, mostK);
				   if(relFileList.size()>=mostK)
				   {
					   kth_score=searchHelper.getMinScore(relFileList);//更新最小相关分数
				   }
				   currNode=currNode.getLeft();
				}
				// 不是叶子节点，计算相关性
				else {
					double score=searchHelper.getScore(currNode.getEnIndex(), trapdoor);
					count++;
					//满足此条件继续向下访问
					if(score>kth_score)
					{
						if(currNode.getRight()!=null)
						{
							stack.push(currNode.getRight());
						}
						currNode=currNode.getLeft();
					}
					else {
						currNode=null;
					}
				}
			}
			else {
				currNode=stack.pop();
			}
		}
		System.out.println("所有计算相关分数的节点个数是："+count);
		return relFileList;
	}
	public List<fileScorePair>searchOverTreeTravel(indexTreeNode node,encryptedIndex trapdoor,int mostK)
	{
		List<fileScorePair>relFileList=new ArrayList<fileScorePair>();
		double kth_score=0;
		int count=0;
		indexTreeNode currNode=node;
		if(currNode.getLeft()!=null&&currNode.getRight()!=null)//如果当前节点不是叶子节点
		{
			double score=searchHelper.getScore(currNode.getEnIndex(), trapdoor);
			count++;
			if(score>kth_score)
			{
				searchOverTreeTravel(currNode.getLeft(), trapdoor, mostK);
				searchOverTreeTravel(currNode.getRight(), trapdoor, mostK);
			}
		}
		else
		{
			
		}
		return relFileList;
	}
	/**
	 * 得到叶子节点的总个数
	 * @param root
	 * @return
	 */
	public int getLeafCount(indexTreeNode root)
	{
		int count=0;
		indexTreeNode currNode=root;
		Queue<indexTreeNode>queue=new LinkedBlockingQueue<>();
		if(currNode!=null)
		{
			queue.add(currNode);
		}
		while(!queue.isEmpty())
		{
			currNode=queue.poll();
			if(currNode.getLeft()==null&&currNode.getRight()==null)
			{
				count++;
			}
			if(currNode.getLeft()!=null)
			{
				queue.add(currNode.getLeft());
			}
			if(currNode.getRight()!=null)
			{
				queue.add(currNode.getRight());
			}
		}
		return count;
	}
	public indexTreeNode getChangedNode(indexTreeNode node)
	{
		indexTreeNode resultNode=null;
		int deepth=getTreeDepth(node);
		Queue<indexTreeNode>queue=new LinkedList<indexTreeNode>();
		indexTreeNode currNode=node;
		if(currNode!=null)
		{
			queue.add(currNode);
		}
		while(!queue.isEmpty())
		{
			currNode=queue.poll();
			if(getNodeHeight(currNode)<deepth)
			{
				if(currNode.getLeft()==null&&currNode.getRight()==null)
				{
					resultNode=currNode;
					break;
				}
				else {
					if(currNode.getLeft()!=null)
					{
						queue.add(currNode.getLeft());
					}
					if(currNode.getRight()!=null)
					{
						queue.add(currNode.getRight());
					}
				}
			}
		}
		if(resultNode==null)
		{
			resultNode=getALeafNode(node);
		}
		return resultNode;
	}
	public int getNodeHeight(indexTreeNode node)
	{
		int height=0;
		indexTreeNode currNode=node;
		while(currNode!=null)
		{
			if(currNode==root)
			{
				height++;
				break;
			}
			currNode=currNode.getParent();
			height++;
			
		}
		return height;
		
	}
	
	
}